Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Chromatic Number
Graph Decomposition
Perfect Graph
Polynomial Time
Subscribe
Academic
Publications
Evenholefree graphs that do not contain diamonds: A structure theorem and its consequences
Evenholefree graphs that do not contain diamonds: A structure theorem and its consequences,10.1016/j.jctb.2008.12.005,Journal of Combinatorial Theor
Edit
Evenholefree graphs that do not contain diamonds: A structure theorem and its consequences
(
Citations: 5
)
BibTex

RIS

RefWorks
Download
Ton Kloks
,
Haiko Müller
,
Kristina Vuskovic
In this paper we consider the class of simple graphs defined by excluding, as induced subgraphs, even holes (i.e., chordless cycles of even length) and diamonds (i.e., a graph obtained from a clique of size 4 by removing an edge). We say that such graphs are (evenhole, diamond)free. For this class of graphs we first obtain a decomposition theorem, using clique cutsets, bisimplicial cutsets (which is a special type of a star cutset) and 2joins. This decomposition theorem is then used to prove that every graph that is (evenhole, diamond)free contains a simplicial extreme (i.e., a vertex that is either of degree 2 or whose neighborhood induces a clique). This characterization implies that for every (evenhole, diamond)free graph G, χ(G)⩽ω(G)+1 (where χ denotes the
chromatic number
and ω the size of a largest clique). In other words, the class of (evenhole, diamond)free graphs is a χbounded family of graphs with the Vizing bound for the chromatic number.The existence of simplicial extremes also shows that (evenhole, diamond)free graphs are βperfect, which implies a
polynomial time
coloring algorithm, by coloring greedily on a particular, easily constructable, ordering of vertices. Note that the class of (evenhole, diamond)free graphs can also be recognized in polynomial time.
Journal:
Journal of Combinatorial Theory  JCT
, vol. 99, no. 5, pp. 733800, 2009
DOI:
10.1016/j.jctb.2008.12.005
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.sciencedirect.com
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
(
linkinghub.elsevier.com
)
More »
Citation Context
(1)
...Several such decomposition results were obtained in recent years, including those for Meyniel graphs [5], perfect graphs [7], capfree graphs [10], universally signable graphs [14], evenholefree graphs [12], certain subclass of oddholefree graphs [9], and (diamond, even hole)free graphs [
23
]...
Ferdinando Cicalese
,
et al.
Graphs of Separability at Most Two: Structural Characterizations and T...
References
(14)
Bisimplicial vertices in evenholefree graphs
(
Citations: 3
)
Louigi Addarioberry
,
Maria Chudnovsky
,
Frédéric Havet
,
Bruce A. Reed
,
Paul D. Seymour
Journal:
Journal of Combinatorial Theory  JCT
, vol. 98, no. 6, pp. 11191164, 2008
Characterizations of derived graphs
(
Citations: 40
)
L BEINEKE
Journal:
Journal of Combinatorial Theory
, vol. 9, no. 2, pp. 129135, 1970
The strong perfect graph theorem
(
Citations: 193
)
Maria Chudnovsky
,
Neil Robertson
,
Paul Seymour
,
Robin Thomas
Journal:
Annals of Mathematics  ANN MATH
, vol. 164, no. 1, pp. 51229, 2006
Even and odd holes in cap‐free graphs
(
Citations: 6
)
Michele Conforti
,
Gérard Cornuéjols
,
Ajai Kapoor
,
Kristina Vušković
Journal:
Journal of Graph Theory  JGT
, vol. 30, no. 4, pp. 289308, 1999
EvenHoleFree Graphs Part II: Recognition Algorithm
(
Citations: 16
)
Michele Conforti
,
Gérard Cornuéjols
,
Ajai Kapoor
,
Kristina Vuskovic
Journal:
Journal of Graph Theory  JGT
, 2000
Sort by:
Citations
(5)
P01565  Functional impairment prevalence in Brazilian frailty elderly
A. S. Ferreira
,
E. M. S. Barbosa
,
N. R. B. Raposo
,
W. F. Gattaz
Journal:
European Psychiatry  EUR PSYCHIAT
, vol. 26, pp. 569569, 2011
P01453  Abridged cultural formulation of a clinical case
I. Garcia del Castillo
,
L. Caballero Martinez
Journal:
European Psychiatry  EUR PSYCHIAT
, vol. 26, pp. 457457, 2011
P02484  Psychiatric disorders among children living in orphanages  experience from Kashmir
Y. Rather
Journal:
European Psychiatry  EUR PSYCHIAT
, vol. 26, pp. 10801080, 2011
Graphs of Separability at Most Two: Structural Characterizations and Their Consequences
Ferdinando Cicalese
,
Martin Milanic
Published in 2010.
Combinatorial optimization with 2joins
Nicolas Trotignon
,
Kristina Vuÿskovic
Journal:
Journal of Combinatorial Theory  JCT