{"id":2714,"date":"2024-07-01T10:25:32","date_gmt":"2024-07-01T13:25:32","guid":{"rendered":"https:\/\/icc.fcen.uba.ar\/?p=2714"},"modified":"2024-07-01T10:25:32","modified_gmt":"2024-07-01T13:25:32","slug":"thinness-and-its-variations-on-some-graph-families-and-coloring-graphs-of-bounded-thinness","status":"publish","type":"post","link":"https:\/\/icc.fcen.uba.ar\/en\/thinness-and-its-variations-on-some-graph-families-and-coloring-graphs-of-bounded-thinness\/","title":{"rendered":"Thinness and its variations on some graph families and coloring graphs of bounded thinness"},"content":{"rendered":"<div class=\"fusion-fullwidth fullwidth-box fusion-builder-row-1 fusion-flex-container has-pattern-background has-mask-background nonhundred-percent-fullwidth non-hundred-percent-height-scrolling\" style=\"--awb-border-radius-top-left:0px;--awb-border-radius-top-right:0px;--awb-border-radius-bottom-right:0px;--awb-border-radius-bottom-left:0px;--awb-flex-wrap:wrap;\" ><div class=\"fusion-builder-row fusion-row fusion-flex-align-items-flex-start fusion-flex-content-wrap\" style=\"max-width:1144px;margin-left: calc(-4% \/ 2 );margin-right: calc(-4% \/ 2 );\"><div class=\"fusion-layout-column fusion_builder_column fusion-builder-column-0 fusion_builder_column_1_1 1_1 fusion-flex-column\" style=\"--awb-bg-size:cover;--awb-width-large:100%;--awb-margin-top-large:0px;--awb-spacing-right-large:1.92%;--awb-margin-bottom-large:20px;--awb-spacing-left-large:1.92%;--awb-width-medium:100%;--awb-order-medium:0;--awb-spacing-right-medium:1.92%;--awb-spacing-left-medium:1.92%;--awb-width-small:100%;--awb-order-small:0;--awb-spacing-right-small:1.92%;--awb-spacing-left-small:1.92%;\"><div class=\"fusion-column-wrapper fusion-column-has-shadow fusion-flex-justify-content-flex-start fusion-content-layout-column\"><div class=\"fusion-text fusion-text-1\"><p>Authors: Flavia Bonomo-Braberman, Eric Brandwein, Fabiano S. Oliveira, Moys\u00e9s S. Sampaio Jr., Agustin Sansone and Jayme L. Szwarcfiter.<\/p>\n<p>Abstract:<br \/>\nInterval graphs and proper interval graphs are well known graph classes, for which several generalizations have been proposed in the literature. In this work, we study the (proper) thinness, and several variations, for the classes of cographs, crowns graphs and grid graphs.<br \/>\nWe provide the exact values for several variants of thinness (proper, independent, complete, precedence, and combinations of them) for the crown graphs CRn. For cographs, we prove that the precedence thinness can be determined in polynomial time. We also improve known bounds for the thinness of n\u00d7n grids GRn and m\u00d7n grids GRm,n, proving that \u2308n\u221213\u2309\u2264thin(GRn)\u2264\u2308n+12\u2309. Regarding the precedence thinness, we prove that prec-thin(GRn,2)=\u2308n+12\u2309 and that \u2308n\u221213\u2309\u2308n\u221212\u2309+1\u2264prec-thin(GRn)\u2264\u2308n\u221212\u23092+1. As applications, we show that the k-coloring problem is NP-complete for precedence 2-thin graphs and for proper 2-thin graphs, when k is part of the input. On the positive side, it is polynomially solvable for precedence proper 2-thin graphs, given the order and partition.<\/p>\n<p>More information:\u00a0<a href=\"https:\/\/arxiv.org\/abs\/2303.06070\" target=\"_blank\" rel=\"noopener\">https:\/\/arxiv.org\/abs\/2303.06070<\/a><\/p>\n<\/div><\/div><\/div><\/div><\/div>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":9,"featured_media":2715,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[98],"tags":[],"class_list":["post-2714","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-papers"],"_links":{"self":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2714","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/users\/9"}],"replies":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/comments?post=2714"}],"version-history":[{"count":1,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2714\/revisions"}],"predecessor-version":[{"id":2716,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2714\/revisions\/2716"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media\/2715"}],"wp:attachment":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media?parent=2714"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/categories?post=2714"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/tags?post=2714"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}