Lifted, projected and subgraph-induced inequalities for the representatives -fold coloring polytope

详细信息    查看全文

• 作者：Manoel Campê ; lo^a ; ^{mcampelo@lia.ufc.br" class="auth_mail" title="E-mail the corresponding author} ; Phablo F.S. Moura^b ; ^{phablo@ime.usp.br" class="auth_mail" title="E-mail the corresponding author} ; Marcio C. Santos^c ; ^{marcio.santos@utc.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：(kk-fold) graph coloring ; Stable set polytope ; Facet ; Web graph ; Lexicographic product
• 刊名：Discrete Optimization
• 出版年：2016
• 出版时间：August 2016
• 年：2016
• 卷：21
• 期：Complete
• 页码：131-156
• 全文大小：1017 K

文摘

A 7252861630041X&_mathId=si1.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=3a690f14e8fad38d8e838a29084d1763" title="Click to view the MathML source">k$k$-fold 7252861630041X&_mathId=si2.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=930470b6bf07eaf2d0cbf1bae271427a" title="Click to view the MathML source">x$x$-coloring of a graph 7252861630041X&_mathId=si26.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=f759a2fffa5023864394d01308114306" title="Click to view the MathML source">G$G$ is an assignment of (at least) 7252861630041X&_mathId=si1.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=3a690f14e8fad38d8e838a29084d1763" title="Click to view the MathML source">k$k$ distinct colors from the set 7252861630041X&_mathId=si28.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=08ed734d976b98c4cb8dc792651c7990" title="Click to view the MathML source">{1,2,…,x}$\{1,2,\dots ,x\}$ to each vertex such that any two adjacent vertices are assigned disjoint sets of colors. The 7252861630041X&_mathId=si1.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=3a690f14e8fad38d8e838a29084d1763" title="Click to view the MathML source">k$k$th chromatic number of 7252861630041X&_mathId=si26.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=f759a2fffa5023864394d01308114306" title="Click to view the MathML source">G$G$, denoted by 7252861630041X&_mathId=si31.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=603754e13c80a9c03502512f048b2079" title="Click to view the MathML source">χ_k(G)${\chi }_k\left(G\right)$, is the smallest 7252861630041X&_mathId=si2.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=930470b6bf07eaf2d0cbf1bae271427a" title="Click to view the MathML source">x$x$ such that 7252861630041X&_mathId=si26.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=f759a2fffa5023864394d01308114306" title="Click to view the MathML source">G$G$ admits a 7252861630041X&_mathId=si1.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=3a690f14e8fad38d8e838a29084d1763" title="Click to view the MathML source">k$k$-fold 7252861630041X&_mathId=si2.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=930470b6bf07eaf2d0cbf1bae271427a" title="Click to view the MathML source">x$x$-coloring. We present an integer linear programming formulation (ILP) to determine 7252861630041X&_mathId=si31.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=603754e13c80a9c03502512f048b2079" title="Click to view the MathML source">χ_k(G)${\chi }_k\left(G\right)$ and study the facial structure of the corresponding polytope 7252861630041X&_mathId=si37.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=16eadd027b949367b02688fab3799f31" title="Click to view the MathML source">P_k(G)${\mathcal{P}}_k\left(G\right)$. We show facets that 7252861630041X&_mathId=si38.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=29835fe441640bf15b6a35060763a924" title="Click to view the MathML source">P_k+1(G)${\mathcal{P}}_{k+1}\left(G\right)$ inherits from 7252861630041X&_mathId=si37.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=16eadd027b949367b02688fab3799f31" title="Click to view the MathML source">P_k(G)${\mathcal{P}}_k\left(G\right)$ and show how to lift facets from 7252861630041X&_mathId=si37.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=16eadd027b949367b02688fab3799f31" title="Click to view the MathML source">P_k(G)${\mathcal{P}}_k\left(G\right)$ to 7252861630041X&_mathId=si41.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=12b22862d847877a0276c4eeccb7a869" title="Click to view the MathML source">P_k+ℓ(G)${\mathcal{P}}_{k+\ell }\left(G\right)$. We project facets of 7252861630041X&_mathId=si42.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=86e1b1fb6c47fd54b69174261ffc71a8" title="Click to view the MathML source">P₁(G∘K_k)${\mathcal{P}}_1(G\circ K_k)$ into facets of 7252861630041X&_mathId=si37.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=16eadd027b949367b02688fab3799f31" title="Click to view the MathML source">P_k(G)${\mathcal{P}}_k\left(G\right)$, where 7252861630041X&_mathId=si44.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=8d9ee9b72a4847e06252f920f43db45f" title="Click to view the MathML source">G∘K_k$G\circ K_k$ is the lexicographic product of 7252861630041X&_mathId=si26.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=f759a2fffa5023864394d01308114306" title="Click to view the MathML source">G$G$ by a clique with 7252861630041X&_mathId=si1.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=3a690f14e8fad38d8e838a29084d1763" title="Click to view the MathML source">k$k$ vertices. In both cases, we can obtain facet-defining inequalities from many of those known for the 7252861630041X&_mathId=si47.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=e71f33191a139d2d8dff4da219575672" title="Click to view the MathML source">1$1$-fold coloring polytope. We also derive facets of 7252861630041X&_mathId=si37.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=16eadd027b949367b02688fab3799f31" title="Click to view the MathML source">P_k(G)${\mathcal{P}}_k\left(G\right)$ from facets of stable set polytopes of subgraphs of 7252861630041X&_mathId=si26.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=f759a2fffa5023864394d01308114306" title="Click to view the MathML source">G$G$. In addition, we present classes of facet-defining inequalities based on strongly 7252861630041X&_mathId=si50.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=4a09e6519d033fb050017c121707f1bd" title="Click to view the MathML source">χ_k${\chi }_k$-critical webs and antiwebs, which extend and generalize known results for 7252861630041X&_mathId=si47.gif&_user=111111111&_pii=S157252861630041X&_rdoc=1&_issn=15725286&md5=e71f33191a139d2d8dff4da219575672" title="Click to view the MathML source">1$1$-fold coloring. We introduce this criticality concept and characterize the webs and antiwebs having such a property.