Cubicity of Interval Graphs and the Claw Number
Copyright policy )Cubicity of Interval Graphs and the Claw Number
AbstractAn odd hole in a graph is an induced cycle of odd length at least five. In this article we show that every imperfect K4‐free graph with no odd hole either is one of two basic graphs, or has an even pair or a clique cutset. We use this result to show that every K4‐free graph with no odd hole has circular chromatic number strictly smaller than 4. We also exhibit a sequence {Hn} of such graphs with limn→∞χc(Hn)=4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 303–322, 2010
- King’s University United States
- Columbia University United States
- Ryerson University Canada
- Sobolev Institute of Mathematics Russian Federation
- Siberian Branch of the Russian Academy of Sciences Russian Federation
Computer Science & Automation (Formerly, Computer Science & Automation (Formerly, School of Automation), FOS: Mathematics, 511, Mathematics - Combinatorics, School of Automation), Combinatorics (math.CO)
Computer Science & Automation (Formerly, Computer Science & Automation (Formerly, School of Automation), FOS: Mathematics, 511, Mathematics - Combinatorics, School of Automation), Combinatorics (math.CO)
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).22 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!