Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStrongly Perfect Claw-free Graphs -- A Short Proof
304
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A graph is strongly perfect if every induced subgraph H has a stable set that meets every maximal clique of H. A graph is claw-free if no vertex has three pairwise non-adjacent neighbors. The characterization of claw-free graphs that are strongly perfect by a set of forbidden induced subgraphs was conjectured by Ravindra in 1990 and was proved by Wang in 2006. Here we give a shorter proof of this characterization.
rate research
Read More
A emph{$k$--bisection} of a bridgeless cubic graph $G$ is a $2$--colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes have order at most $k$. Ban and Linial conjectured that {em every bridgeless cubic graph admits a $2$--bisection except for the Petersen graph}. In this note, we prove Ban--Linials conjecture for claw--free cubic graphs.
A cycle $C$ of length $k$ in graph $G$ is extendable if there is another cycle $C$ in $G$ with $V(C) subset V(C)$ and length $k+1$. A graph is cycle extendable if every non-Hamiltonian cycle is extendable. In 1990 Hendry conjectured that any Hamiltonian chordal graph (a Hamiltonian graph with no induced cycle of length greater than three) is cycle extendable, and this conjecture has been verified for Hamiltonian chordal graphs which are interval graphs, planar graphs, and split graphs. We prove that any 2-connected claw-free chordal graph is cycle extendable.
A graph is strongly perfect if every induced subgraph H has a stable set that meets every nonempty maximal clique of H. The characterization of strongly perfect graphs by a set of forbidden induced subgraphs is not known. Here we provide several new minimal non-strongly-perfect graphs.
A short proof is given that the graphs with proper interval representations are the same as the graphs with unit interval representations.
The second authors $omega$, $Delta$, $chi$ conjecture proposes that every graph satisties $chi leq lceil frac 12 (Delta+1+omega)rceil$. In this paper we prove that the conjecture holds for all claw-free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way we discuss a stronger local conjecture, and prove that it holds for claw-free graphs with a three-colourable complement. To prove our results we introduce a very useful $chi$-preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so-called skeletal graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
