Coloring (4K1,C4,C6)-free graphs

被引：0
作者：
Penev, Irena [1 ]
机构：
[1] Charles Univ IUUK, Comp Sci Inst, Prague, Czech Republic
来源：
DISCRETE MATHEMATICS | 2023年 / 346卷 / 11期
关键词：
(4K(1); C-4; C-6)-free graphs; Even-hole-free graphs; Graph Coloring; Maximal cliques; Minimum clique cover; HOLE-FREE GRAPHS; DECOMPOSITION;
D O I：
10.1016/j.disc.2022.113225
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
(4K(1),C-4,C-6)-free graphs are precisely the even-hole-free graphs of stability number at most three. We show that (4K(1),C-4,C-6)-free graphs can be recognized in (n(3)) time, and furthermore, that all the following can be computed in (n(3)) time for such graphs: an optimal coloring, a minimum clique cover, and the list of all maximal cliques. We also show that every (4K(1),C-4,C-6)-free graph on n vertices has at most n maximal cliques.@2022 Elsevier B V All rights reserved.
引用
收藏
页数：34
相关论文
共 20 条
  • [1] Even-hole-free graphs Part II:: Recognition algorithm
    Conforti, M
    Cornuëjols, G
    Kapoor, A
    Vuskovic, K
    [J]. JOURNAL OF GRAPH THEORY, 2002, 40 (04) : 238 - 266
  • [2] Even-hole-free graphs part I:: Decomposition theorem
    Conforti, M
    Cornuéjols, G
    Kapoor, A
    Vuskovic, K
    [J]. JOURNAL OF GRAPH THEORY, 2002, 39 (01) : 6 - 49
  • [3] Triangulated neighborhoods in even-hole-free graphs
    da Silva, Murilo V. G.
    Vuskovic, Kristina
    [J]. DISCRETE MATHEMATICS, 2007, 307 (9-10) : 1065 - 1073
  • [4] Decomposition of even-hole-free graphs with star cutsets and 2-joins
    da Silva, Murilo V. G.
    Vuskovic, Kristina
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2013, 103 (01) : 144 - 183
  • [5] Dirac G. A., 1961, MATH SEM U HAMB, V25, P71, DOI [10.1007/BF02992776, DOI 10.1007/BF02992776]
  • [6] ON DIAMETERS AND RADII OF BRIDGED GRAPHS
    FARBER, M
    [J]. DISCRETE MATHEMATICS, 1989, 73 (03) : 249 - 260
  • [7] The Intersection of Two Vertex Coloring Problems
    Foley, Angele M.
    Fraser, Dallas J.
    Hoang, Chinh T.
    Holmes, Kevin
    LaMantia, Tom P.
    [J]. GRAPHS AND COMBINATORICS, 2020, 36 (01) : 125 - 138
  • [8] Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring
    Fomin, Fedor, V
    Golovach, Petr A.
    Lokshtanov, Daniel
    Saurabh, Saket
    Zehavi, Meirav
    [J]. ACM TRANSACTIONS ON ALGORITHMS, 2019, 15 (01)
  • [9] INCIDENCE MATRICES AND INTERVAL GRAPHS
    FULKERSON, DR
    GROSS, OA
    [J]. PACIFIC JOURNAL OF MATHEMATICS, 1965, 15 (03) : 835 - +
  • [10] Gavril F., 1972, SIAM Journal on Computing, V1, P180, DOI 10.1137/0201013
12