Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA note on 2--bisections of claw--free cubic graphs
199
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Let $Oct_{1}^{+}$ and $Oct_{2}^{+}$ be the planar and non-planar graphs that obtained from the Octahedron by 3-splitting a vertex respectively. For $Oct_{1}^{+}$, we prove that a 4-connected graph is $Oct_{1}^{+}$-free if and only if it is $C_{6}^{2}$, $C_{2k+1}^{2}$ $(k geq 2)$ or it is obtained from $C_{5}^{2}$ by repeatedly 4-splitting vertices. We also show that a planar graph is $Oct_{1}^{+}$-free if and only if it is constructed by repeatedly taking 0-, 1-, 2-sums starting from ${K_{1}, K_{2} ,K_{3}} cup mathscr{K} cup {Oct,L_{5} }$, where $mathscr{K}$ is the set of graphs obtained by repeatedly taking the special 3-sums of $K_{4}$. For $Oct_{2}^{+}$, we prove that a 4-connected graph is $Oct_{2}^{+}$-free if and only if it is planar, $C_{2k+1}^{2}$ $(k geq 2)$, $L(K_{3,3})$ or it is obtained from $C_{5}^{2}$ by repeatedly 4-splitting vertices.
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 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.
Resolving a conjecture of Furedi from 1988, we prove that with high probability, the random graph $G(n,1/2)$ admits a friendly bisection of its vertex set, i.e., a partition of its vertex set into two parts whose sizes differ by at most one in which $n-o(n)$ vertices have at least as many neighbours in their own part as across. The engine of our proof is a new method to study stochastic processes driven by degree information in random graphs; this involves combining enumeration techniques with an abstract second moment argument.
The 1-2-3 Conjecture, posed by Karo{n}ski, {L}uczak and Thomason, asked whether every connected graph $G$ different from $K_2$ can be 3-edge-weighted so that every two adjacent vertices of $G$ get distinct sums of incident weights. The 1-2 Conjecture states that if vertices also receive colors and the vertex color is added to the sum of its incident edges, then adjacent vertices can be distinguished using only ${ 1,2}$. In this paper we confirm 1-2 Conjecture for 3-regular graphs. Meanwhile, we show that every 3-regular graph can achieve a neighbor sum distinguishing edge coloring by using 4 colors, which answers 1-2-3 Conjecture positively.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
